package leetcode.editor.cn;

import java.util.*;

//[49]字母异位词分组
public class GroupAnagrams49 {
    public static void main(String[] args) {

        System.out.println("GroupAnagrams49:main: a x b越界：" + (Integer.MAX_VALUE / 2 * Integer.MAX_VALUE / 3));
        Solution solution = new GroupAnagrams49().new Solution();


    }


    //在一般领域，对正整数n，如果用2到  之间的所有整数去除，均无法整除，则n为质数。
    public static boolean testIsPrime2(int n) {
        if (n <= 3) {
            return n > 1;
        }

        for (int i = 2; i < n; i++) {
            if (n % i == 0)
                return false;
        }
        return true;
    }

    /*优化后*/
    public static boolean testIsPrime3(int n) {
        if (n <= 3) {
            return n > 1;
        }

        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0)
                return false;
        }
        return true;
    }

    //2.
    class Prime {
        public void main(String[] args) {
            int a = 17; //判断17是不是质数
            int c = 0;
            for (int b = 2; b < a; b++) {
                if (a % b != 0) {
                    c++;
                }
            }
            if (c == a - 2) {
                System.out.println(a + "是质数");
            } else {
                System.out.println(a + "不是质数");
            }
        }
    }

    /**
     * https://baike.baidu.com/item/质数/263515
     * @title SOE
     * @desc 简单的埃氏筛选法计算素数
     * @author he11o
     * @date 2016年5月3日
     * @version 1.0
     * 采用简单的埃氏筛选法和简单的开方判断素数法计算1000000以内素数的个数的效率比较：
     * StopWatch '计算1000000以内素数的个数': running time （millis） = 268
     * -----------------------------------------
     * ms % Task name
     * -----------------------------------------
     * 00024 009% 简单的埃氏筛选法；
     * 00244 091% 简单的开方判断素数法。
     */
    public static int calPrime(int n) {
        if (n <= 1) {
            return 0;
        }
        byte[] origin = new byte[n + 1];
        int count = 0;
        for (int i = 2; i < n + 1; i++) {
            if (origin[i] == 0) {
                count++;
                int k = 2;
                while (i * k <= n) {
                    origin[i * k] = 1;
                    k++;
                }
            } else {
                continue;
            }
        }
        return count;
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        //思路 质数相乘作为HashMap的键 。防止溢出。溢出有影响么？还是没有。小概率事件。int 相乘。溢出碰撞。
        // 两个质数之积生成的合数不能由另外两个及两个以上质数之积来表示，
        //利用质数的这一性质，给每个小写字母对应一个质数，可以用质数之积来表示一类字母异位词。
        // 执行耗时:4 ms,击败了99.96% 的Java用户
        //			内存消耗:44.4 MB,击败了63.99% 的Java用户
        // 链接：https://leetcode.cn/problems/group-anagrams/solution/javazhi-shu-xiang-cheng-fang-fa-yong-shi-5ms-ji-ba/
        public List<List<String>> groupAnagrams2(String[] strs) {
            List<List<String>> res = new ArrayList<>();
            //判空
            if (strs == null || strs.length == 0) return res;
            List<String> container = null;
            Map<Integer, List<String>> map = new HashMap<>();
            //质数数组
            int[] tab = {3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103};
            //tip值，用来标识一类字母异位词
            int tip;
            char[] str = null;
            for (String s : strs) {
                tip = 1;
                str = s.toCharArray();
                for (int i = 0; i < s.length(); i++) {
                    tip = tip * tab[s.charAt(i) - 'a'];
                }
                if ((container = map.get(tip)) == null) {
                    container = new ArrayList<>();
                }
                container.add(s);
                map.put(tip, container);
            }
            for (List<String> list : map.values()) {
                res.add(list);
            }
            return res;
        }

        //   链接：https://leetcode.cn/problems/group-anagrams/solution/zi-ding-yi-zi-fu-chuan-de-ha-xi-gui-ze-shi-yong-zh/
        //执行耗时:5 ms,击败了98.83% 的Java用户
        // 质数 相乘。。溢出问题的解决。。。？
        public List<List<String>> groupAnagrams(String[] strs) {
            // 考察了哈希函数的基本知识，只要 26 个即可
            // ()小写字母ACSII 码 - 97 )以后和质数的对应规则，这个数组的元素顺序无所谓
            // key 是下标，value 就是数值
            int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
                    31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
                    73, 79, 83, 89, 97, 101};

            //计算hashValue时如果乘积溢出的话能保证哈希值不同吗? ???
            // 这一步。啥意思？？？
            long mod = 1000000000 + 7;

            // key 是字符串自定义规则下的哈希值
            Map<Long, List<String>> hashMap = new HashMap<>();
            for (String s : strs) {
                long hashValue = 1;

                for (int i = 0; i < s.length(); i++) {
                    hashValue = ((hashValue % mod) * (primes[s.charAt(i) - 'a'] % mod)) % mod;
                }

                if (hashMap.containsKey(hashValue)) {
                    List<String> curList = hashMap.get(hashValue);
                    curList.add(s);
                } else {
                    List<String> newList = new ArrayList<>();
                    newList.add(s);

                    hashMap.put(hashValue, newList);
                }
            }
            return new ArrayList<>(hashMap.values());
        }


        //方法一：排序
        //将排序之后的字符串作为哈希表的键。异位词相同。
        //执行耗时:5 ms,击败了98.83% 的Java用户
        public List<List<String>> groupAnagramsOrg(String[] strs) {
            Map<String, List<String>> map = new HashMap<String, List<String>>();
            for (String str : strs) {
                char[] array = str.toCharArray();
                Arrays.sort(array);
                String key = new String(array);
                List<String> list = map.getOrDefault(key, new ArrayList<String>());
                list.add(str);
                map.put(key, list);
            }
            return new ArrayList<List<String>>(map.values());
        }

        //方法二：计数
        //使用长度为 26 的数组记录每个字母出现的次数。作为哈希表的键 26 * 2= 52 长度。
        // 执行耗时:10 ms,击败了26.01% 的Java用户 。比想象的慢。取决于。数组的长度。如果长，应该好用。
        // 链接：https://leetcode.cn/problems/group-anagrams/solution/zi-mu-yi-wei-ci-fen-zu-by-leetcode-solut-gyoc/
        public List<List<String>> groupAnagramsOrg2(String[] strs) {
            Map<String, List<String>> map = new HashMap<String, List<String>>();
            for (String str : strs) {
                int[] counts = new int[26];
                int length = str.length();
                for (int i = 0; i < length; i++) {
                    counts[str.charAt(i) - 'a']++;
                }
                // 将每个出现次数大于 0 的字母和出现次数按顺序拼接成字符串，作为哈希表的键
                StringBuffer sb = new StringBuffer();
                for (int i = 0; i < 26; i++) {
                    if (counts[i] != 0) {
                        sb.append((char) ('a' + i));
                        sb.append(counts[i]);
                    }
                }
                String key = sb.toString();
                List<String> list = map.getOrDefault(key, new ArrayList<String>());
                list.add(str);
                map.put(key, list);
            }
            return new ArrayList<List<String>>(map.values());
        }


    }
//leetcode submit region end(Prohibit modification and deletion)

}